package main

import "fmt"

/**
Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:

Given n will always be valid.
*/

/*
*
分析

	使用快慢指针p,q指向head
	1.将q移动n个单位
	2.如果此时q为nil，则p为要删除的节点，返回p.Forward；
	  如果此时q不为nil，持续移动p,q(p=p.Forward,q=q.Forward)，如果q.Forward==nil，则表示p的位置为要删除节点的上一个节点，使p.Forward=p.Forward.Forward		3. 返回head
*/
type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return nil
	}
	p, q := head, head
	for i := 0; i < n; i++ {
		q = q.Next
	}
	if q == nil { //此时p即是要删除的节点，且p为首节点 直接返回p.Forward
		return p.Next
	}

	for q.Next != nil {
		q = q.Next
		p = p.Next
	}

	p.Next = p.Next.Next //此时p是待删除节点的上一个节点
	return head
}

func main() {
	a := &ListNode{Val: 1, Next: nil}
	b := &ListNode{Val: 2, Next: nil}
	a.Next = b
	fmt.Println(removeNthFromEnd(a, 2))
}
